package 算法题汇总;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        System.out.println("desad");
        BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
        int k = Integer.parseInt(sc.readLine());//表示k组数据
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < k; i++) {
            String[] arr1 = sc.readLine().split(" ");
            int [] arr = new int[3];
            for (int j = 0; i < 3; i++) {
                arr[i] = Integer.parseInt(arr1[i]);
            }
            int[][] edge = new int[arr[1]][3];
            for (int m = 0; m < arr[1]; m++) {
                String[] arr2 = sc.readLine().split(" ");
                for (int aa = 0; aa < 3; aa++) {
                    edge[m][aa] = Integer.parseInt(arr2[aa]);
                }
            }
            int i1 = find(arr[0], edge, arr[2]);
            result.append(i1);
            System.out.println(result.toString());
        }
    }
    public static int find(int n, int [][] edge,int distance){
        int [][] map = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(i == j){
                    map[i][j] = 0;
                }else{
                    map[i][j] = Integer.MAX_VALUE;
                }
            }
        }
        for(int [] a:edge){
            map[a[0]][a[1]] = map[a[1]][a[0]] = a[2];
        }
        for(int k = 0;k < n;k++){
            for(int i =0;i<n;i++){
                for(int j = 0;j<n;j++){
                    if(i != k && map[i][k] != Integer.MAX_VALUE && map[k][j] != Integer.MAX_VALUE){
                        map[i][j] = Math.min(map[i][j],map[i][k]+map[k][j]);
                    }
                }
            }
        }

        int min = n+1;
        int res = -1;
        for(int i = 0;i<n;i++){
            int count = 0;
            for (int j = 0; j < n; j++) {
                if(i != j && map[i][j] <= distance){
                    count++;
                }
            }
            if(min >= count){
                min = count;
                res = i;
            }
        }
        return res;
    }
}
